% $Header: /home/vedranm/bitbucket/beamer/solutions/conference-talks/conference-ornate-20min.en.tex,v 90e850259b8b 2007/01/28 20:48:30 tantau $

\documentclass{beamer}

\mode<presentation>
{
  \usetheme{Warsaw}
  \setbeamercovered{transparent}
}


\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}

\newcommand{\setblue}[1]{\textcolor{blue!50!black}}

\title{On Abelian Repetition Threshold}

\author[Alexey V. Samsonov, Arseny M. Shur] % (optional, use only with lots of authors)
{Alexey  V.~Samsonov \and Arseny M.~Shur}

\institute[Ural State University] % (optional, but mostly needed)
{
  Ural State University\\
  Ekaterinburg, Russia}

\date[JM 2010] % (optional, should be abbreviation of conference name)
{
13th Mons Theoretical Computer Science Days\\
Amiens, France, September 9th, 2010}


% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

\pgfdeclareimage[height=0.5cm]{university-logo}{usu_symbol}
\logo{\pgfuseimage{university-logo}}


%\AtBeginSection[]
%{
%  \begin{frame}<beamer>{Outline}
%    \tableofcontents[currentsection,currentsubsection]
%  \end{frame}
%}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

%\begin{frame}{Outline}
%  \tableofcontents
%\end{frame}

\section{Preliminaries}

\begin{frame}{Powers of Words}
	\begin{itemize}
		\item Recall that the \alert{$m$-th power} of a word \textcolor{black}{$u \in \Sigma^{*}$} is just
			\textcolor{black}{$u$} repeated \textcolor{black}{$m$} times.
		\item Let \textcolor{black}{$\beta > 1$}. \textcolor{black}{$u = u_1u_2 \ldots u_mv$} is a \alert{$\beta$-power} if:
			\begin{itemize}
				\item \textcolor{black}{$u_1 = u_2 = \ldots = u_m$}, \textcolor{black}{$m = \lfloor \beta \rfloor$};
				\item \textcolor{black}{$|v| = \lceil \{ \beta \}|u_1| \rceil$};
				\item \textcolor{black}{$v$} is a prefix of \textcolor{black}{$u_1$}.
			\end{itemize}
			In that case \textcolor{black}{$\beta$} is called an \alert{exponent} of a word \textcolor{black}{$u$}.
	\end{itemize}
	\begin{block}{Examples}<2->
		\begin{itemize}
			\item \alert{templa te} has exponent \textcolor{black}{4/3}.
			\item \alert{abc abc a} is a \textcolor{black}{7/3}-power as well as \textcolor{black}{7/6}-power.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Avoidable Powers}
	\begin{itemize}
		\item A word \textcolor{black}{$u$} is \alert{$\beta$-free} (\alert{$\beta^{+}$-free})
			if exponents of all its factors are less than \textcolor{black}{$\beta$} (not greater than \textcolor{black}{$\beta$}).
		\item A \textcolor{black}{$\beta$}-power is \alert{$k$-avoidable} if there are infinitely many \textcolor{black}{$\beta$}-free words
			over the \textcolor{black}{$k$}-letter alphabet, and \alert{$k$-unavoidable} otherwise.
		\item The \alert{Repetition threshold} is a number \alert{$RT(k)$} which separates \textcolor{black}{$k$}-unavoidable
			and \textcolor{black}{$k$}-avoidable exponents.
	\end{itemize}
	\begin{block}{Conjecture[Dejean, 1972]}<2->
		\begin{itemize}
			\item \textcolor{black}{$RT(3) = 7/4$},
			\item \textcolor{black}{$RT(4) = 7/5$},
			\item \textcolor{black}{$RT(k) = k/(k-1)$} for all \textcolor{black}{$k \geqslant 5$}.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Integral Abelian Powers}
	\begin{itemize}
		\item A word \textcolor{black}{$u_1u_2 \ldots u_n$} is an \alert{Abelian $n$-th power} if each of the words
			\textcolor{black}{$u_2$}, \ldots, \textcolor{black}{$u_n$} is an anagram of \textcolor{black}{$u_1$}.
		\item In terms of \alert{Parikh vectors} we can write \textcolor{black}{$\vec p(u_1) = \ldots = \vec p(u_n)$}.
	\end{itemize}
	\begin{block}{Examples}<2->
		\begin{itemize}
			\item \alert{acab bcaa} is an Abelian \textcolor{black}{2nd} power (or \textcolor{black}{square}).
			\item \alert{abba abab baba} is an Abelian \textcolor{black}{3rd} power (or \textcolor{black}{cube})
				as well as Abelian \textcolor{black}{square}.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Avoidance of Abelian Integral Powers}
	\begin{itemize}
		\item We can define the notion of \textcolor{black}{$k$}-avoidability for integral Abelian powers in the same way.
		\item<2-> The number of \alert{binary 4-free} words is infinite \textcolor{green!50!black}{[Dekking, 1979]}
			and grows exponentially \textcolor{green!50!black}{[Currie, 2004]}.
		\item<3-> The number of \alert{ternary cube-free} words is infinite \textcolor{green!50!black}{[Dekking, 1979]} and grows
			exponentially \textcolor{green!50!black}{[Aberkane, Currie, Rampersad, 2004]}.
		\item<4-> The number of \alert{quarternary square-free} words is infinite \textcolor{green!50!black}{[Ker\"anen, 1992]} and grows
			exponentially \textcolor{green!50!black}{[Carpi, 1998]}.
	\end{itemize}
\end{frame}

\begin{frame}{Open Questions}
	\begin{itemize}
		\item How \alert{``big''} the languages of Abelian power-free words are?
		\item What is a \alert{fractional} Abelian power?
		\item What is an \alert{Abelian repetition threshold}?
	\end{itemize}
\end{frame}

\begin{frame}{Growth Rate}
	\begin{itemize}
		\item \alert{Combinatorial complexity} of a language \textcolor{black}{$L$} is the function
			\textcolor{black}{$C_L(n) = |\Sigma^n\cap L|$}.
		\item \alert{Growth rate} of \textcolor{black}{$L$} is defined as
			\textcolor{black}{$\alpha(L) = \limsup\limits_{n\to\infty}(C_L(n))^{1/n}$}.
		\item \textcolor{black}{$\alpha(L) = 0$} for finite languages and \textcolor{black}{$\alpha(L) > 1$} for languages with
			exponential growth.
	\end{itemize}
	\begin{block}{Remark}<2->
		We calculate \alert{upper bounds} for the growth rates of Abelian power-free languages.
	\end{block}
\end{frame}

\begin{frame}{Antidictionaries}
	\begin{itemize}
		\item \alert{Antidictionary $M$} of a factorial language \textcolor{black}{$L$} is a set of all minimal (w.r.t. factorization
			order) forbidden words for \textcolor{black}{$L$}.
		\item \textcolor{black}{$M=\Sigma L\cap L\Sigma\cap(\Sigma^*{-}L)$}
		\item \textcolor{black}{$L=\Sigma^*-\Sigma^*\!M\Sigma^*$}
	\end{itemize}
	\begin{block}{Remark}<2->
		The Abelian power-free languages are not regular and their \alert{antidictionaries are infinite}.
	\end{block}
\end{frame}

\begin{frame}{Main Algorithm}
	We use a method for calculating upper bounds for the growth rates of arbitrary factorial languages described in
	\textcolor{green!50!black}{[Shur, Growth rates of complexity of power free-languages, Theor. Comp. Sci. \textbf{411} (2010), 3209-3223]}.
	\begin{enumerate}
		\item<2-> Generate a \alert{finite approximation} \textcolor{black}{$\bar{M}$} of antidictionary \textcolor{black}{$M$}.
		\item<2-> Store all words in \textcolor{black}{$\bar{M}$} in a \alert{trie}.
		\item<2-> Construct a \alert{dfa} \textcolor{black}{$\cal A$} recognizing the language defined by \textcolor{black}{$\bar{M}$}.
		\item<2-> The growth rate of that language coincides with the \alert{Frobenius root} of the adjacency matrix
			of \textcolor{black}{$\cal A$}.
	\end{enumerate}
\end{frame}

\begin{frame}{Comments on the Algorithm}
	\begin{enumerate}
		\item We can calculate the Frobenius root of a matrix with \alert{any prescribed precision}.
		\item Construction of dfa and calculation of the growth rate \alert{work rather fast} for all dfa's that can be stored
			in the memory.
		\item The main problem is \alert{generating antidictionaries} of Abelian power-free languages.
	\end{enumerate}
\end{frame}

\section{Antidictionaries of Abelian Power-free Languages}

\begin{frame}{Fractional Abelian Powers}
	Let \textcolor{black}{$\beta > 1$}. \textcolor{black}{$u = u_1u_2 \ldots u_mv$} is an \alert{Abelian $\beta$-power} if:
		\begin{itemize}
			\item \textcolor{black}{$\vec p(u_1) = \vec p(u_2) = \ldots = \vec p(u_m)$},
				\textcolor{black}{$m = \lfloor \beta \rfloor$},
				\textcolor{black}{$u_1$} is a \alert{root};
			\item \textcolor{black}{$|v| = \lceil \{\beta\}|u_1| \rceil$},
				\textcolor{black}{$v$} is a \alert{tail};
			\item What are the restrictions for \textcolor{black}{$\vec p(v)$}?
		\end{itemize}
	\begin{block}{}
		\begin{itemize}
			\item<2-> \alert{Weak} powers: \textcolor{black}{$\vec p(v) \leqslant \vec p(u_1)$},
				i.e. tail is a \alert{prefix of an anagram}.
			\item<3-> \alert{Strong} powers: \textcolor{black}{$\vec p(v) = \vec p(\mathrm{pref}(u_1, |v|))$},
				i.e. tail is an \alert{anagram of prefix}.
			\item<4-> \alert{Semistrong} powers:
				\textcolor{black}{$\vec p(v) \leqslant \bigvee\limits_{i=\overline{1,m}}\!\!\vec p(\mathrm{pref}(u_i,|v|))$}, where
				\textcolor{black}{$\bigvee$} is a \alert{componentwise maximum}.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Examples of Fractional Abelian Powers}
	\begin{block}{Remarks}
		\begin{enumerate}
			\item For \textcolor{black}{$\beta \leqslant 2$} semistrong $<=>$ strong.
			\item strong $=>$ semistrong $=>$ weak.
		\end{enumerate}
	\end{block}
	\begin{block}{Examples}<2->
		\begin{itemize}
			\item \alert{bana na} is a weak (but not a semistrong or strong) Abelian \textcolor{black}{$(3/2)$}-power
			\item \alert{abc cba ac} is a weak and semistrong (but not a strong) Abelian \textcolor{black}{$(8/3)$}-power
			\item \alert{baob ab} is a weak, semistrong and strong Abelian \textcolor{black}{$(3/2)$}-power
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Minimal Forbidden Abelian Powers}
	\begin{block}{Question}
		What is the length of \alert{minimal forbidden} word \textcolor{black}{$u$} with a root of length \textcolor{black}{$r$}?
		\begin{itemize}
			\item<2-> \textcolor{black}{$|u| = \lceil \beta \cdot r \rceil$} for \alert{weak} powers
			\item<2-> \textcolor{black}{$\lceil \beta \cdot r \rceil \leqslant |u| \leqslant \lceil \beta \rceil \cdot r$}
				for \alert{strong} and \alert{semistrong} powers.
		\end{itemize}
	\end{block}
	\begin{block}{Example}<3->
		\alert{abcde bdaec} is a \alert{minimal} forbidden word for strong Abelian-\textcolor{black}{$(7/5)$}-free language.
	\end{block}
	\begin{block}{Remark}<4->
		The length of an Abelian power is determined by the lengths of its root and its tail.
	\end{block}
\end{frame}

\begin{frame}{Algorithm Outline}
	\begin{enumerate}
		\item Store all potential roots of minimal forbidden words in a \alert{queue}.
		\item \alert{Extend} each potential root by \alert{recursively} appending letters to it until a minimal forbidden word is obtained.
		\item After appending each letter we check that a current word contains no \alert{forbidden suffices} (in linear or quadratic time).
	\end{enumerate}
\end{frame}

\section{Numerical Results}

\begin{frame}{Upper Bounds for the Growth Rates}
	\begin{table}[!htb]
		\centerline{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			$|\Sigma|$ & Exponent & AD size & Growth rate \\
			\hline
			2 & 4 & 9M & 1.374 \\
			\hline
			3 & 3 & 6M & 2.371 \\
			\hline
			4 & 2 & 4M & 1.444 \\
			\hline
			5  & 2 & 6M & 3.227 \\
			\hline
		\end{tabular}
		}
	\end{table}
\end{frame}

\begin{frame}{Upper Bounds for the Growth Rates}
	\begin{table}[!htb]
		\centerline{
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			$|\Sigma|$ & Type & Exponent & AD size & Growth rate \\
			\hline
			2 & weak & $(11/3)^{+}$ & 16M & 1.067 \\
			\hline
			2 & semi & $(11/3)^{+}$ & 12M & 1.138 \\
			\hline
			2 & strong & $(11/3)^{+}$ & 16M & 1.233 \\
			\hline
			3 & --- & 2 & 7 & 0.000 \\
			\hline
			3 & semi & $2^{+}$ & 3M & 1.295 \\
			\hline
			3 & strong & $2^{+}$ & 12M & 1.646 \\
			\hline
			5 & weak & $5/3$ & 18K & 0.000 \\
			\hline
			5 & weak & $(5/3)^{+}$ & 18M & 1.686 \\
			\hline
			5 & strong & $3/2$ & 49 & 0.000 \\
			\hline
			5 & strong & $(3/2)^{+}$ & 7M & 2.335 \\
			\hline
		\end{tabular}
		}
	\end{table}
\end{frame}

\begin{frame}{Conjectured Abelian Repetition Thresholds}
	\begin{table}[!htb]
		\centerline{
		\begin{tabular}{|c|c|c|c|}
			\hline
			$|\Sigma|$ & \phantom{zzz}weak\phantom{zzz} & semistrong & \phantom{zz}strong\phantom{zz} \\
			\hline
			2 & 11/3 ? & 11/3 & 11/3 \\
			\hline
			3 & 17/7 ? & 2 & 2 \\
			\hline
			4 & 15/8 ? & 9/5 & 9/5 \\
			\hline
			5 & 5/3 & 3/2 & 3/2 \\
			\hline
		\end{tabular}
		}
	\end{table}
\end{frame}

\begin{frame}{Abelian Repetiton Threshold for Strong Powers}
	\begin{block}{Theorem}
		For \textcolor{black}{$k \geqslant 5$} exponent \textcolor{black}{$(k-2)/(k-3)$} is \textcolor{black}{$k$}-unavoidable in case of
		strong Abelian powers.
	\end{block}
	\begin{block}{Conjecture}<2->
		\alert{Abelian repetition threshold} for \alert{strong} (and \alert{semistrong}) Abelian powers:
		\begin{itemize}
			\item \textcolor{black}{$ART_s(2) = 11/3$},
			\item \textcolor{black}{$ART_s(3) = 2$},
			\item \textcolor{black}{$ART_s(4) = 9/5$},
			\item \textcolor{black}{$ART_s(k) = (k-2)/(k-3)$} for all \textcolor{black}{$k \geqslant 5$}.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}
\centerline{\alert{Thank you!}}
\end{frame}


\end{document}


